#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

class Node {
 public:
  Node(int _key = 0) : key(_key), cnt(1) {}

  static constexpr int kMaxHeight = 12;
  int ne[kMaxHeight];
  int height;
  int key;
  int cnt;
};

class Skiplist {
 public:
  static constexpr int N = 20005;
  Node tr[N];
  int idx_no_use;
  int max_height;

  Skiplist() : max_height(1), idx_no_use(2) {
    tr[0].key = -1;
    tr[0].height = Node::kMaxHeight;
    for (int i = 0; i < Node::kMaxHeight; ++i) tr[0].ne[i] = 1;
    tr[1].key = 2e9;
    tr[1].height = Node::kMaxHeight;
  }

  int FindGreaterOrEqual(int target, int* prev = nullptr) {
    int cur_height = max_height - 1;
    int cur_node = 0;
    while (true) {
      if (cur_height < 0) {
        cur_node = tr[cur_node].ne[0];
        if (tr[cur_node].key == target)
          return cur_node;
        else
          return -1;
      }
      if (tr[tr[cur_node].ne[cur_height]].key < target) {
        cur_node = tr[cur_node].ne[cur_height];
      } else {
        if (prev) prev[cur_height] = cur_node;
        --cur_height;
      }
    }
  }

  bool search(int target) { return FindGreaterOrEqual(target) != -1; }

  void add(int num) {
    int prev[Node::kMaxHeight];
    int target_node = FindGreaterOrEqual(num, prev);
    if (target_node != -1) {
      ++tr[target_node].cnt;
      return;
    }
    int new_node = idx_no_use++;
    int height_new_node = getRandomHeight();
    tr[new_node].height = height_new_node;
    tr[new_node].key = num;
    for (int i = max_height; i < height_new_node; ++i) prev[i] = 0;
    for (int i = 0; i < height_new_node; ++i) {
      tr[new_node].ne[i] = tr[prev[i]].ne[i];
      tr[prev[i]].ne[i] = new_node;
    }
    max_height = max(max_height, height_new_node);
  }

  bool erase(int num) {
    int prev[Node::kMaxHeight];
    int target_node = FindGreaterOrEqual(num, prev);
    if (target_node == -1) return false;
    if (tr[target_node].cnt > 1) {
      --tr[target_node].cnt;
    } else {
      for (int i = 0; i < tr[target_node].height; ++i) {
        tr[prev[i]].ne[i] = tr[target_node].ne[i];
      }
    }
    return true;
  }

 private:
  int getRandomHeight() {
    int ans = 1;
    while (ans < Node::kMaxHeight && rand() % 2 == 0) {
      ++ans;
    }
    return ans;
  }
};

/**
 * Your Skiplist object will be instantiated and called as such:
 * Skiplist* obj = new Skiplist();
 * bool param_1 = obj->search(target);
 * obj->add(num);
 * bool param_3 = obj->erase(num);
 */

int main() {
  Skiplist* obj = new Skiplist();

  vector<int> paras = {
      -1, 16, 5, 14, 13, 0,  3,  12, 9, 12, 3,  6,  7,  0,  1,  10, 5,  12, 7,
      16, 7,  0, 9,  16, 3,  2,  17, 2, 17, 0,  9,  14, 1,  6,  1,  16, 9,  10,
      9,  2,  3, 16, 15, 12, 7,  4,  3, 2,  1,  14, 13, 12, 3,  6,  17, 2,  3,
      14, 11, 0, 13, 2,  1,  10, 17, 0, 5,  8,  9,  8,  11, 10, 11, 10, 9,  8,
      15, 14, 1, 6,  17, 16, 13, 4,  5, 4,  17, 16, 7,  14, 1};
  vector<string> ops = {
      "Skiplist", "add",    "add",    "add",    "add",    "add",    "add",
      "add",      "add",    "add",    "erase",  "search", "add",    "erase",
      "erase",    "erase",  "add",    "search", "search", "search", "erase",
      "search",   "add",    "add",    "add",    "erase",  "search", "add",
      "search",   "erase",  "search", "search", "erase",  "erase",  "add",
      "erase",    "search", "erase",  "erase",  "search", "add",    "add",
      "erase",    "erase",  "erase",  "add",    "erase",  "add",    "erase",
      "erase",    "add",    "add",    "add",    "search", "search", "add",
      "erase",    "search", "add",    "add",    "search", "add",    "search",
      "erase",    "erase",  "search", "search", "erase",  "search", "add",
      "erase",    "search", "erase",  "search", "erase",  "erase",  "search",
      "search",   "add",    "add",    "add",    "add",    "search", "search",
      "search",   "search", "search", "search", "search", "search", "search"};

  cout << "null,";
  for (int i = 0; i < ops.size(); ++i) {
    if (ops[i] == "add") {
      obj->add(paras[i]);
      cout << "null,";
    } else if (ops[i] == "erase") {
      auto ans = obj->erase(paras[i]);
      if (ans)
        cout << "true,";
      else
        cout << "false,";
    } else if (ops[i] == "search") {
      auto ans = obj->search(paras[i]);
      if (ans)
        cout << "true,";
      else
        cout << "false,";
    }
  }
  return 0;
}